package StudyCode.summary.mycollection;

/**
 * 版权所有 科技与人文(www.tah1986.com)
 */
public class ComputesTheMedianOfAnArray {
	public static void main(String[] argv) {
		double[] v = new double[]{34.45, 35.45, 36.67, 37.78, 37.0000,
				37.1234, 67.2344, 68.34534, 69.87700};
		System.out.println("数组中位数是:" + median(v));
	}


	public static double median(double[] v) {
		if (v.length == 3) {
			return median3(copy(v));
		} else if (v.length == 5) {
			return median5(copy(v));
		} else if (v.length == 7) {
			return median7(copy(v));
		} else if (v.length % 2 == 1) {
			return quickSelect(copy(v), false);
		} else {
			double[] tmp = copy(v);
			double lowerMedian = quickSelect(tmp, false);
			double upperMedian = quickSelect(tmp, true);
			return (lowerMedian + upperMedian) / 2.0;
		}
	}

	private static double median3(double[] v) {
		sortInPlace(v, 0, 1);
		sortInPlace(v, 1, 2);
		sortInPlace(v, 0, 1);
		return v[1];
	}

	private static int median3(int[] v) {
		sortInPlace(v, 0, 1);
		sortInPlace(v, 1, 2);
		sortInPlace(v, 0, 1);
		return v[1];
	}

	public static int[] copy(int[] array) {
		int[] result;
		result = new int[array.length];
		System.arraycopy(array, 0, result, 0, array.length);
		return result;
	}

	public static long[] copy(long[] array) {
		long[] result;
		result = new long[array.length];
		System.arraycopy(array, 0, result, 0, array.length);
		return result;
	}

	public static float[] copy(float[] array) {
		float[] result;
		result = new float[array.length];
		System.arraycopy(array, 0, result, 0, array.length);
		return result;
	}

	public static double[] copy(double[] array) {
		double[] result;
		result = new double[array.length];
		System.arraycopy(array, 0, result, 0, array.length);
		return result;
	}

	public static double[][] copy(double[][] v) {
		double[][] ans = new double[v.length][];
		for (int k = 0; k < v.length; k++)
			ans[k] = copy(v[k]);
		return (ans);
	}

	public static int[][] copy(int[][] v) {
		int[][] ans = new int[v.length][];
		for (int k = 0; k < v.length; k++)
			ans[k] = copy(v[k]);
		return (ans);
	}

	private static double median5(double[] v) {
		sortInPlace(v, 0, 1);
		sortInPlace(v, 3, 4);
		sortInPlace(v, 0, 3);
		sortInPlace(v, 1, 4);
		sortInPlace(v, 1, 2);
		sortInPlace(v, 2, 3);
		sortInPlace(v, 1, 2);
		return v[2];
	}

	private static double median7(double[] v) {
		sortInPlace(v, 0, 5);
		sortInPlace(v, 0, 3);
		sortInPlace(v, 1, 6);
		sortInPlace(v, 2, 4);
		sortInPlace(v, 0, 1);
		sortInPlace(v, 3, 5);
		sortInPlace(v, 2, 6);
		sortInPlace(v, 2, 3);
		sortInPlace(v, 3, 6);
		sortInPlace(v, 4, 5);
		sortInPlace(v, 1, 4);
		sortInPlace(v, 1, 3);
		sortInPlace(v, 3, 4);
		return v[3];
	}

	private static double quickSelect(double[] v, boolean upperMedian) {
		int low = 0, high = v.length - 1;
		final int median = upperMedian ? high / 2 + 1 : high / 2;
		int middle, ll, hh;

		for (; ; ) {
			if (high <= low) {
				return v[median];
			}

			if (high == low + 1) {
				if (v[low] > v[high])
					swap(v, low, high);
				return v[median];
			}

			middle = (low + high) / 2;
			if (v[middle] > v[high])
				swap(v, middle, high);
			if (v[low] > v[high])
				swap(v, low, high);
			if (v[middle] > v[low])
				swap(v, middle, low);

			swap(v, middle, low + 1);

			ll = low + 1;
			hh = high;
			for (; ; ) {
				do
					ll++;
				while (v[low] > v[ll]);
				do
					hh--;
				while (v[hh] > v[low]);

				if (hh < ll)
					break;

				swap(v, ll, hh);
			}

			swap(v, low, hh);

			if (hh <= median)
				low = ll;
			if (hh >= median)
				high = hh - 1;
		}
	}

	private static void sortInPlace(final double[] v, final int i,
	                                final int j) {
		if (v[i] > v[j]) {
			final double tmp = v[i];
			v[i] = v[j];
			v[j] = tmp;
		}
	}

	private static void sortInPlace(final int[] v, final int i, final int j) {
		if (v[i] > v[j]) {
			final int tmp = v[i];
			v[i] = v[j];
			v[j] = tmp;
		}
	}

	private static void swap(final double a[], final int i, final int j) {
		final double T;
		T = a[i];
		a[i] = a[j];
		a[j] = T;

	}
}
